#include <cstring>
#include <linux/limits.h>
class Solution {
public:
    int minMoney(vector<int>& arr, int aim) {
        //背包dp问题，对于背包问题创建的状态为
        //dp[i][j]代表从前i个物品中进行选择，总值等于j，我选择的最少物品个数为多少1
        int len = arr.size();
        if(len == 0)
        {
            return -1;
        }
        int dp[len+1][aim+1];
        memset(dp,0,sizeof(dp));
        for(int i = 1;i<=aim;i++)
        {
            dp[0][i] = 0x3f3f3f3f;
        }
        dp[0][0] = 0;
        for(int i = 1;i<=len;i++)
        {
            for(int j = 0;j<=aim;j++)
            {
                dp[i][j] = dp[i-1][j];
                if(j-arr[i-1]>=0)
                {
                    dp[i][j] = min(dp[i][j],dp[i][j-arr[i-1]]+1);
                }
            }
        }
        return dp[len][aim] == 0x3f3f3f3f?-1:dp[len][aim];
    }
};